package exp3;

import java.util.Stack;

class Box                        //方块结构体类型
{
    int i;                        //方块的行号
    int j;                        //方块的列号
    int di;                        //di是下一可走相邻方位的方位号

    public Box(int i1, int j1, int di1)    //构造方法
    {
        i = i1;
        j = j1;
        di = di1;
    }
}

class MazeClass                                            //用栈求解所有迷宫路径类
{
    final int MaxSize = 20;
    int[][] mg;                                        //迷宫数组
    int m, n;                                            //迷宫行列数
    int cnt = 0;                                            //迷宫路径条数

    public MazeClass(int m1, int n1)                        //构造方法
    {
        m = m1;
        n = n1;
        mg = new int[MaxSize][MaxSize];
    }

    public void Setmg(int[][] a)                        //设置迷宫数组
    {
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                mg[i][j] = a[i][j];
    }

    public int mgpath(int xi, int yi, int xe, int ye)        //求一条从(xi,yi)到(xe,ye)的迷宫路径
    {
        int i, j, di, i1 = 0, j1 = 0;
        boolean find;
        Box box, e;
        Stack<Box> st = new Stack<Box>();                    //建立一个空栈
        st.push(new Box(xi, yi, -1));                        //入口方块进栈
        mg[xi][yi] = -1;                                    //进栈方块的mg置为-1
        while (!st.empty())                                //栈不空时循环
        {
            box = st.peek();                                //取栈顶方块,称为当前方块
            i = box.i;
            j = box.j;
            di = box.di;
            if (i == xe && j == ye)                            //找到了出口,输出一条迷宫路径
            {
                Stack<Box> tmpst = new Stack<Box>();        //建立临时栈
                cnt++;                                    //路径条数增1
                System.out.print("  迷宫路径" + cnt + ": ");//输出一条迷宫路径
                while (!st.empty()) {
                    e = st.pop();
                    System.out.print("[" + e.i + "," + e.j + "]  ");
                    tmpst.push(e);                        //出栈元素进tmpst栈
                }
                while (!tmpst.empty())                    //tmpst栈中元素出栈并进st栈
                    st.push(tmpst.pop());
                System.out.println();
                box = st.pop();                            //退栈st
                mg[box.i][box.j] = 0;                        //让该位置变为其他路径可走方块
                i = box.i;
                j = box.j;
                di = box.di;
            }
            find = false;                                    //否则继续找路径
            while (di < 4 && !find)                        //找下一个相邻可走方块
            {
                di++;                                    //找下一个方位的相邻方块
                switch (di) {
                    case 0:
                        i1 = i - 1;
                        j1 = j;
                        break;
                    case 1:
                        i1 = i;
                        j1 = j + 1;
                        break;
                    case 2:
                        i1 = i + 1;
                        j1 = j;
                        break;
                    case 3:
                        i1 = i;
                        j1 = j - 1;
                        break;
                }
                if (mg[i1][j1] == 0) find = true;                            //找到下一个可走相邻方块(i1,j1)
            }
            if (find)                                    //找到了下一个可走方块
            {
                e = st.pop();
                e.di = di;
                st.push(e);                                //修改栈顶元素的di字段为di
                st.push(new Box(i1, j1, -1));                //下一个可走方块进栈
                mg[i1][j1] = -1;                            //进栈方块的mg置为-1
            } else                                        //没有路径可走,则退栈
            {
                mg[i][j] = 0;                                //恢复当前方块的迷宫值
                st.pop();                                //将栈顶方块退栈
            }
        }
        return cnt;                                        //返回迷宫路径条数
    }
}

public class MazeSolver {
    public static void main(String[] args) {

        int[][] a = {{1, 1, 1, 1, 1, 1}, {1, 0, 1, 0, 0, 1}, {1, 0, 0, 1, 1, 1}, {1, 0, 1, 0, 0, 1}, {1, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1}};

        MazeClass mz = new MazeClass(6, 6);
        System.out.println();
        mz.Setmg(a);
        int cnt = mz.mgpath(1, 1, 4, 4);
        if (cnt == 0) System.out.println("  不存在迷宫路径");
        else System.out.println("  共计" + cnt + "条迷宫路径");
    }
} 
